#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/10/26 18:02
# ===========================================
#       题目名称： 63. 不同路径 II
#       题目地址： https://leetcode.cn/problems/unique-paths-ii/description/
#       题目描述： https://note.youdao.com/s/VjIUrvCD
# ===========================================
from typing import *


class Solution:
    """
        0   0       1   1
        1   1       0   0
        0   0
    """

    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # 获取列表size
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        # 定义动态规划数据
        dp = [[0] * n for _ in range(m)]
        # 初始化起点
        dp[0][0] = 1
        for x in range(m):
            for y in range(n):
                if obstacleGrid[x][y] == 1:
                    dp[x][y] = 0  # 对其进行清空当前步数
                    continue
                t, l = 0, 0
                if x - 1 > -1 and y - 1 > -1:
                    l = dp[x - 1][y]
                    t = dp[x][y - 1]
                    dp[x][y] = t + l
                else:
                    if x - 1 > -1:
                        dp[x][y] = dp[x - 1][y]
                        continue
                    if y - 1 > -1:
                        dp[x][y] = dp[x][y - 1]
                        continue

        return dp[m - 1][n - 1]


if __name__ == '__main__':
    s = Solution()
    # 2
    print("obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] => ", s.uniquePathsWithObstacles(obstacleGrid=[[0, 0, 0], [0, 1, 0], [0, 0, 0]]))
    # 1
    print("obstacleGrid = [[0,1],[0,0]] => ", s.uniquePathsWithObstacles(obstacleGrid=[[0, 1], [0, 0]]))
    # 0
    print("obstacleGrid = [[1]] => ", s.uniquePathsWithObstacles(obstacleGrid=[[1]]))
    # 0
    print("obstacleGrid = [[0,0],[1,1],[0,0]] => ", s.uniquePathsWithObstacles(obstacleGrid=[[0, 0], [1, 1], [0, 0]]))
